package main

import (
	"fmt"
)

/*
排序介绍：
排序是将一组数据，依指定的顺序进行排列的过程
排序分类：
1）内部排序
指将需要处理的所有数据都加载到内部存储器(内存)中进行排序
包括（交换式排序法，选择式排序法，和插入式排序法）
交换式排序法：
交换式排序属于内部排序法，是运用数据值比较后，依判断规则对数据位置进行交换
，以达到排序目的
a:冒泡排序（Bubble sort）
冒泡规则：
b:快速排序（Quick sort）

2）外部排序
数据量过大，无法全部加载到内存中，需要借助外部存储进行排序，包括（合并排序法和直接合并排序法）
*/

func main() {
	//arr := []int{4, 6, 2, 3, 1, 0, 78, 90, 1233}
	//fmt.Println(BubbleSort(arr))
	//fmt.Println(ChooseSort(arr))
	//当存储中文字符的时候最好使用rune类型，因为中文一般都超过了255，然后byte就存不下,直接报 overflows byte
	var name rune
	name = '魇'
	//fmt.Println(name) 打印出的是ASCII值
	fmt.Printf("%c\n", name) //格式化输出
	//fmt.Println(InsertSort(arr))
}

/**
冒泡排序
*/
func BubbleSort(sortData []int) []int {
	/*
		优化方案：
	*/
	//循环整个数组的长度
	for j := 0; j < len(sortData); j++ {
		//这儿只是第一轮找出（最大的那个数，并移动到最末尾）
		for i := 0; i < len(sortData)-1; i++ {
			//控制索引范围
			if i < len(sortData)-1 {
				if sortData[i] > sortData[i+1] {
					temp := sortData[i+1]       //取出后一个索引的值
					sortData[i+1] = sortData[i] //将前一个索引的值，存入后一位索引位置
					sortData[i] = temp          //将之前存入temp的sortData[i+1]存给sortData[i]
				}
			}
		}
	}

	return sortData
}

/**
选择排序
*/
func ChooseSort(sortData []int) []int {
	/*
		arr [4,5,1,7]int
		第一次：从arr[0]~arr[n-1]中找出一个最小or最大的元素，然后将该元素和arr[0]交换
		第二次：从arr[1]~arr[n-1]中找出一个最小or最大的元素，然后将该元素和arr[1]交换
		第三次：从arr[2]~arr[n-1]中找出一个最小or最大的元素，然后将该元素和arr[2]交换
		依次类推
	*/

	/*
		 怎么找arr[n]~arr[n-1]中的最小值or最大值？
		 首先：假设 最大值or最小值 min or max=0
		 然后循环 arr
		 每次 取出 arr[i] 和  min or  max 比较
		 如果 arr[i]<min  min=arr[i]  OR  arr[i]>max max=arr[i]
		 循环完成后 就能找出 min OR  max

				//for i := 0; i < len(sortData); i++ {
				//	if sortData[i] < min {
				//		min = sortData[i]
				//	}
				//}
	*/

	// 如果 假定 arr[0] 作为 最大 or 最小
	var min int = sortData[0]
	var minindex int
	//var max int=sortData[0]

	for j := 0; j < len(sortData); j++ {
		//这轮循环 只是找出 最小值
		for i := j; i < len(sortData); i++ {
			if sortData[i] < min {
				min = sortData[i]
				minindex = i
			}
		}
		//此时 最小值就是 min 同时 要知道 i 是多少，后面 才晓得 交换位置的 索引
		//交换位置
		sortData[minindex] = sortData[j]
		sortData[j] = min
		//此时必须重置 min的值，因为 下一轮的搜索范围是 arr[i+1]~arr[n-1]，搜索范围已经改变，所以min就必须重置为
		//下一轮搜索范围的第一个元素的值
		if j < len(sortData)-1 {
			min = sortData[j+1]
		}

	}

	return sortData

}

/**
  插入排序
*/
func InsertSort(sortData []int) []int {

	/*
			 解析：[1,2,3,4,0,9] 利用插入排序 从大到小 排序
			插入排序是在 一个数组内完成，不需要单独再去开辟一个数组

		    [1,2,3,4,0,9] 默认将第一个元素[1] 作为有序列表的第一个元素
								    注意：
								    将【待插入的元素值 存到 insertVal 变量】
							        将【接收待插入的元素索引 insertIndex 变量，注意 insertIndex 指向的是 待插入元素索引的前面一个位置】
								    eg:=[1,2,3,4,0,9]
								    第一轮：
								    insertVal:=eg[1]
								    insertIndex=1-1
								    循环判断找可以插入到有序列表的位置
								    for insertIndex>=0 && eg[insertIndex]<insertVal{
							            数据后移
								        这一轮需要把有序列表中的 1 后移一位
								        此时insertIndex是指向的有序列表的1这个元素，后移一位就是 insertIndex+1
								        eg[insertIndex+1]=eg[insertIndex]
								    }
								    //查找有序列表完成，插入数据

								    if insertIndex+1!=1{
								     eg[insertIndex+1]=insertVal
								    }
							       第二轮：
						               insertVal:=eg[2]
									    insertIndex=2-1
									    循环判断找可以插入到有序列表的位置
									    for insertIndex>=0 && eg[insertIndex]<insertVal{
								            数据后移
									        这一轮需要把有序列表中的 1 后移一位
									        此时insertIndex是指向的有序列表的1这个元素，后移一位就是 insertIndex+1
									        eg[insertIndex+1]=eg[insertIndex]
									    }
									    //查找有序列表完成，插入数据

									    if insertIndex+1!=2{
									     eg[insertIndex+1]=insertVal
									    }
								       第三轮：
						               insertVal:=eg[3]
									    insertIndex=3-1
									    循环判断找可以插入到有序列表的位置
									    for insertIndex>=0 && eg[insertIndex]<insertVal{
								            数据后移
									        这一轮需要把有序列表中的 1 后移一位
									        此时insertIndex是指向的有序列表的1这个元素，后移一位就是 insertIndex+1
									        eg[insertIndex+1]=eg[insertIndex]
									    }
									    //查找有序列表完成，插入数据
				                        //如果正好等于 待插入元素的索引 说明 刚好就是 在有序列表的最后一个元素的 后面，那就没必要去插入
									    if insertIndex+1!=3{
									     eg[insertIndex+1]=insertVal
									    }
	*/

	for i := 1; i <= len(sortData)-1; i++ {
		insertVal := sortData[i] //待插入的值
		insertIndex := i - 1     //待插入的索引位置（为啥要-1？因为：[1,2,4] 索引-1 正好就是 有序列表的 最后一个元素（因为你要跟 有序列表 从右至左 一直比较），）

		//因为要 【一直比较】 所以要用 循环（注意要考虑退出的条件）
		for insertIndex >= 0 && sortData[insertIndex] < insertVal {
			sortData[insertIndex+1] = sortData[insertIndex] //数据后移
			insertIndex--                                   //移动指针继续在有序列表中查找
		}
		//插入（insertValue）

		if insertIndex+1 != i {
			sortData[insertIndex+1] = insertVal
		}
	}
	return sortData
}

/**
快速排序
*/
//func QuickSort(sortData []int) []int {
//
//}
